package offer;

/**
 * @Author Elephas
 * @Date 2022/1/28
 **/
@FunctionalInterface

public interface Search2 {
    /**
     * 搜索旋转排序数组 II
     * @param nums
     * @param target
     * @return
     */
    boolean search(int[] nums,int target);
}


class Search2Impl1 implements Search2{
    /**
     * 实现思路：
     * 二分查找
     * @param nums
     * @param target
     * @return
     */
    @Override
    public boolean search(int[] nums, int target) {
        return searchHelper(nums,target,0, nums.length - 1);

    }
    private boolean searchHelper(int[] nums,int target,int left,int right){
        int low = left, high = right;
        int mid = 0;
        while(low <= high){
            mid = low + (high - low) / 2;
            boolean cond1 = nums[low] < nums[mid] && nums[high] < nums[mid];
            if(cond1 && nums[mid] < target){
                low = mid + 1;
            }else if(cond1 && nums[mid] > target){
                return searchHelper(nums,target,low,mid - 1) || searchHelper(nums,target,mid + 1,high);
            }else if(cond1 && nums[mid] == target){
                break;
            }
            boolean cond2 = nums[low] > nums[mid] && nums[mid] < nums[high];
            if(cond2 && nums[mid] > target){
                high = mid -1;
            }else if(cond2 && nums[mid] < target){
                return searchHelper(nums,target,low,mid - 1) || searchHelper(nums,target,mid + 1,high);
            }else if(cond2 && nums[mid] == target){
                break;
            }
        }
        if(low <= high){
            return true;
        }else{
            return false;
        }
    }
}
class Search2Impl2 implements  Search2{
    final static int[] TEST_01 = new int[]{1};
    final static int[] TEST_02 = new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1};
    final static int[] TEST_03 = new int[]{3,1,1};
    final static int[] TEST_04 = new int[]{1,1,1,1,1,1,1,1,1,13,1,1,1,1,1,1,1,1,1,1,1,1};
    public static void main(String[] args) {
        new Search2Impl2().search(TEST_04,13);
    }

    @Override
    public boolean search(int[] nums, int target) {
        return searchHelper(nums,target,0, nums.length - 1);
    }
    private boolean searchHelper(int[] nums,int target,int left,int right){
        int low = left, high = right;
        int mid = 0;
        if(left > right)
            return false;
        mid = low + (high - low) / 2;
        if(nums[left] == nums[right] && nums[left] != target){
            return searchHelper(nums, target, left + 1, right - 1);
        }else {
            if (target > nums[mid]) {
                return searchHelper(nums, target, mid + 1, right);
            } else if (target == nums[mid]) {
                return true;
            } else {
                return searchHelper(nums, target, left, mid - 1) || searchHelper(nums, target, mid + 1, right);
            }
        }
    }
}
